class Solution(object):
    def constructDistancedSequence(self, n):
        ans = [0] * (2 * n - 1)
        used = [0] * n
        m = len(ans)

        def dfs(i):
            if i == m:
                return True
            if ans[i]:
                return dfs(i + 1)
            for j in range(n - 1, -1, -1):
                if not used[j]:
                    if j == 0:
                        ans[i] = j + 1
                        used[j] = 1
                        if dfs(i + 1):
                            return True
                        used[j] = 0
                        ans[i] = 0
                    else:
                        if i + j + 1 < m and not ans[i + j + 1]:
                            ans[i + j + 1] = j + 1
                            ans[i] = j + 1
                            used[j] = 1
                            if dfs(i + 1):
                                return True
                            used[j] = 0
                            ans[i] = 0
                            ans[i + j + 1] = 0
        dfs(0)
        return ans

data = Solution()
print(data.constructDistancedSequence(3))